삽입 정렬

삽입 정렬은 정렬된 상태의 영역을 확대해 나가면서 그 다음의 후보가 삽입될 위치를 찾아 삽입한 뒤 그 다음 원소들을 밀어내는 방식으로 동작한다.

처음의 영역의 크기는 1로 가장 첫번째 원소만 포함한다. 위의 그림을 보면 5라는 원소가 크기 1인 영역에 속해 있고 2라는 다음 원소를 이 영역에 집어 넣는데 이 영역의 원소들과 비교해서 더 큰 숫자를 만나면 그 숫자의 전에 집어넣고 그 뒤로는 밀어낸다. 결과 2가 5의 앞으로 오고 5가 밀려나 2의 자리를 차지한다. 이와 같은 과정을 반복하게 되면 모든 원소들이 삽입되고 정렬된 결과를 얻게된다.

버블 정렬과 마찬가지로 O(n2)의 시간복잡도를 갖는다.

#include<cstdio>
#include<vector>
#include<cstdlib>
#include<ctime>

using namespace std;

void swap(vector<int>& arr, int a, int b)
{
	int temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
}

void InsertSort(vector<int>& arr)
{
	for (int i = 1; i < arr.size(); i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (arr[i] < arr[j])
			{
				int temp = arr[i];
				memcpy(&arr[j+1], &arr[j], sizeof(int*) *(i - j));
				arr[j] = temp;
			}
		}
	}
}
void main()
{
	srand((unsigned int)time(NULL));

	vector<int> arr;
	for (int i = 0; i < 10; i++)
		arr.push_back(rand() % 100);

	InsertSort(arr);

	for (int i = 0; i < 10; i++)
		printf("%d ", arr[i]);
}